package algorithm.poj;

public class DataStructure {

	/**
	 * 最小堆
	 *
	 */
	public static class MinHeap {
		
		int[] array;
		
		public MinHeap(int[] array) {
			this.array = array;
			for (int i = array.length/2; i > -1; i --) heapify(i);
		}
		
		public MinHeap(int size) {
			this.array = new int[size];
		}
		
		@SuppressWarnings("unused")
		private int parent(int i) {
			return (i-1)/2;
		}
		
		private int left(int i) {
			return (i<<1)+1;
		}
		
		private int right(int i) {
			return (i+1)<<1;
		}
		
		private void heapify(int i) {
			
			int min = i;
			int l = left(i);
			if (l < array.length && array[l] < array[i]) {
				min = l;
			}
			int r = right(i);
			if (r < array.length && array[r] < array[min]) {
				min = r;
			}
			if (min != i) {
				int t = array[min];
				array[min] = array[i];
				array[i] = t;
				heapify(min);
			}
		}
		
		public String toString() {
			StringBuffer sb = new StringBuffer("");
			for (int i = 0; i < this.array.length; i++) {
				sb.append(array[i]).append(" ");
			}
			return sb.toString();
		}
	}
	
	public static class Queue<T> {
		
		//用数组模拟一个Queue
		T q[];
		int start;
		int end;
		
		public Queue(T[] array) {
			
			this.q = array;
			for (int i = 0; i < this.q.length; i ++) this.q[i] = null;
			this.start = 0;
			this.end = 0;
		}
		
		public void put(T n) {
			
			int size = this.end-this.start;
			if (size < 0) {
				size += this.q.length;
			}
			if (size == this.q.length-1) {
				throw new RuntimeException("Queue is Full!");
			} else {
				this.q[this.end] = n;
				this.end = (this.end+1)%this.q.length;
			}
		}
		
		public T get() { 
			
			if (this.end == this.start) {
				throw new RuntimeException("Queue is Empty!");
			} else {
				T n = this.q[this.start];
				this.start = (this.start+1)%this.q.length;
				return n;
			}
		}
		
		public boolean isEmpty() {
			return this.end == this.start;
		}
		
		public String toString() {
			
			String s = "[";
			if (this.end > this.start) {
				for (int i = this.start; i < this.end; i ++) {
					if (i > this.start) {
						s += ", ";
					}
					s += this.q[i];
				}
			} else {
				for (int i = this.start; i < this.q.length; i ++) {
					if (i > this.start) {
						s += ", ";
					}
					s += this.q[i];
				}
				for (int i = 0; i < this.end; i ++) {
					s += ", " + this.q[i];
				}
			}
			
			s += "]";
			return s;
		}
	}

}
